/*
 * TopologicalSort.java - Copyright May 14, 2012 Z Networks Group, Inc. All rights reserved.
 * Z Networks Group PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.andromeda.util.dependency;

import java.util.*;

/**
 * Implementación del algoritmo de Arthur B Kahn para el ordenamiento
 * topológico.
 *
 * @author Dickinson Roman Arismendy Torres
 */
public class KahnSorter extends AbstractTopologicalSorter {

    /**
     * {@inheritDoc }
     */
    @Override
    public List<Dependent> sort(Set<? extends Dependent> dependents) {
        return kahnAlgorithm(dependents);
    }
    private List<Dependent> kahnAlgorithm(Set<? extends Dependent> nodes) {
        List<Dependent> L = new ArrayList<Dependent>();
        Queue<Dependent> S = new ArrayDeque<Dependent>(findLastDependents(nodes));
        Set<DependencyEdge> edges = createEdges(nodes);
        while (!S.isEmpty()) {
            Dependent n = S.poll();
            L.add(n);
            for (Dependent m : n.getDependencies()) {
                edges.remove(new DependencyEdge(n, m));
                if (countDependents(edges, m) == 0) {
                    S.add(m);
                }
            }
        }
        if (!edges.isEmpty()) {
            throw new CyclicalDependencyException();
        }
        Collections.reverse(L);
        return L;
    }

    private int countDependents(Set<DependencyEdge> edges, Dependent dependent) {
        int count = 0;
        for (DependencyEdge edge : edges) {
            if (edge.to == dependent || edge.to.equals(dependent)) {
                count++;
            }
        }
        return count;
    }

    private Set<DependencyEdge> createEdges(Set<? extends Dependent> nodes) {
        Set<DependencyEdge> edges = new HashSet<DependencyEdge>();
        for (Dependent from : nodes) {
            for (Dependent to : from.getDependencies()) {
                edges.add(new DependencyEdge(from, to));
            }
        }
        return edges;
    }

    /**
     * Representa un arco en un grafo de dependencias.
     */
    private class DependencyEdge {

        private Dependent from;
        private Dependent to;

        public DependencyEdge(Dependent from, Dependent to) {
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final DependencyEdge other = (DependencyEdge) obj;
            if (this.from != other.from && (this.from == null || !this.from.equals(other.from))) {
                return false;
            }
            if (this.to != other.to && (this.to == null || !this.to.equals(other.to))) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 97 * hash + (this.from != null ? this.from.hashCode() : 0);
            hash = 97 * hash + (this.to != null ? this.to.hashCode() : 0);
            return hash;
        }

        @Override
        public String toString() {
            return from.toString() + " -> " + to.toString();
        }
    }
}
